package chain;

/**
 * 24. 两两交换链表中的节点
 * https://leetcode-cn.com/problems/swap-nodes-in-pairs/
 *
 * 输入：head = [1,2,3,4]
 * 输出：[2,1,4,3]

	 p    h    n
	      1 -> 2 -> 3 -> 4

               p    h    n
 		  2 -> 1 -> 3 -> 4

          			     p    h   n
          2 -> 1 -> 4 -> 3
 *
 */
public class Solution_2 {
	public ListNode swapPairs(ListNode head) {

		// 新增一个前驱节点0
		ListNode p = new ListNode(0);
		p.next = head;

		// 定义一个指针指向前驱节点
		ListNode pre = p;

		while (head != null && head.next != null) {
			ListNode n = head.next;
			head.next = n.next;
			n.next = head;
			pre.next = n;

			//更新指针
			pre = head;
			head = head.next;
		}
		return p.next;
	}


	static class ListNode {
		int val;
		ListNode next;

		ListNode() {
		}

		ListNode(int val) {
			this.val = val;
		}

		ListNode(int val, ListNode next) {
			this.val = val; this.next = next;
		}
	}


	public static void main(String[] args) {

		ListNode listNode = new ListNode(1);
		ListNode listNode2 = new ListNode(2);
		ListNode listNode3 = new ListNode(3);
		ListNode listNode4 = new ListNode(4);
		listNode.next = listNode2;
		listNode2.next = listNode3;
		listNode3.next = listNode4;
		Solution_2 solution_2 = new Solution_2();
		solution_2.swapPairs(listNode);

	}

}
